home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Connect-4 v3.2 / c4.info < prev    next >
Encoding:
Text File  |  1996-07-05  |  10.6 KB  |  228 lines  |  [TEXT/R*ch]
  1. /****************************************************************************/
  2. /**                                                                        **/
  3. /**                          Connect-4 Algorithm                           **/
  4. /**                                                                        **/
  5. /**                              Version 3.2                               **/
  6. /**                                                                        **/
  7. /**                            By Keith Pomakis                            **/
  8. /**                          (pomakis@pobox.com)                           **/
  9. /**                                                                        **/
  10. /**                               June, 1996                               **/
  11. /**                                                                        **/
  12. /****************************************************************************/
  13.  
  14. The files "c4.c" and "c4.h" provide the functions necessary to implement a
  15. front-end-independent, device-independent Connect-4 game.  Multiple board
  16. sizes are supported.  It is also possible to specify the number of pieces
  17. necessary to connect in a row in order to win.  Therefore one can play
  18. Connect-3, Connect-5, etc.  An efficient tree-searching algorithm (making
  19. use of alpha-beta cutoff decisions) has been implemented to insure that the
  20. computer plays as quickly as possible.
  21.  
  22. The file "game.c" is also b/****************************************************************************/
  23. /**                                                                        **/
  24. /**                          Connect-4 Algorithm                           **/
  25. /**                                                                        **/
  26. /**                              Version 3.2                               **/
  27. /**                                                                        **/
  28. /**                            By Keith Pomakis                            **/
  29. /**                          (pomakis@pobox.com)                           **/
  30. /**                                                                        **/
  31. /**                               June, 1996                               **/
  32. /**                                                                        **/
  33. /****************************************************************************/
  34.  
  35. The files "c4.c" and "c4.h" provide the functions necessary to implement a
  36. front-end-independent, device-independent Connect-4 game.  Multiple board
  37. sizes are supported.  It is also possible to specify the number of pieces
  38. necessary to connect in a row in order to win.  Therefore one can play
  39. Connect-3, Connect-5, etc.  An efficient tree-searching algorithm (making
  40. use of alpha-beta cutoff decisions) has been implemented to insure that the
  41. computer plays as quickly as possible.
  42.  
  43. The file "game.c" is also b something other than 0 or 1.
  44.  
  45. Version 3.0 (November, 1995) was a complete overhaul.  Most of the guts
  46. remained the same, and it was just as efficient, but the interface
  47. functions changed.
  48.  
  49. Version 3.1 (May, 1996) fine-tuned some of the innards, making it a whopping
  50. 66% faster (i.e., the computer can now make a move in 1/3 of the time it
  51. used to)!  Minor changes were made to the functional interface.
  52.  
  53. Version 3.2 (June, 1996) fine-tuned the innards a bit more, making it a
  54. bit more efficient.
  55.  
  56.  
  57. Legal Stuff, etc.
  58. -----------------
  59.  
  60. I am releasing these functions to the public domain.  Therefore, people can
  61. use them, copy them, distribute them, modify them, and do whatever they
  62. want with them.
  63.  
  64. If you find any bugs (gasp!) or have any questions or comments about the
  65. functions or about the algorithm itself, you can contact me via e-mail.  My
  66. address is "pomakis@pobox.com".  I'd be interested in hearing what you think!
  67.  
  68. Oh, one other thing... I've put a lot of work into these functions, so I'd
  69. appreciate it if you kept my name attached to them when distributing or
  70. modifying them.  If you actually use these functions for anything, give me
  71. credit somewhere!
  72.  
  73.  
  74. The Algorithm  (not exactly as implemented, but algorithmically equivalent)
  75. -------------
  76.  
  77. All array indexes are zero-based.
  78.  
  79. Global variables:
  80.  
  81.               x = the board width.
  82.  
  83.               y = the board height.
  84.  
  85.               n = the number to connect.
  86.  
  87.        level[2] = the skill level of the computer players, where applicable.
  88.  
  89.     board[x][y] = the board, where board[i][j] contains the value:
  90.                         0 if player 0 occupies position i,j
  91.                         1 if player 1 occupies position i,j
  92.                         C4_NONE if neither player occupies position i,j.
  93.  
  94.               z = the number of possible n-in-a-row areas on the board
  95.                   in which a winning connection can be made.  This equals:
  96.                         4*x*y - 3*x*n - 3*y*n + 3*x + 3*y - 4*n + 2*n*n + 2.
  97.  
  98.                   Each n-in-a-row area on the board in which a winning
  99.                   connection can be made is given a unique number from 0 to
  100.                   z-1.  Each space on the board is told which n-in-a-row
  101.                   areas it is part of.  This is done with the array...
  102.                   
  103.       map[x][y] = an array in which each element is a list specifying, for
  104.                   each corresponding board space, which n-in-a-row areas
  105.                   it is part of.
  106.  
  107.     stats[2][z] = an array containing statistics of each player.  Statistics
  108.                   for player 0 are contained in stats[0], while statistics
  109.                   for player 1 are contained in stats[1].  stats[a][b] will
  110.                   contain 0 if the n-in-a-row area b is no longer a
  111.                   winning possibility for player a.  Otherwise it will
  112.                   contain 2^p, where p is the number of pieces player a has
  113.                   in this area.
  114.  
  115. -----------------------------------------------------------------------------
  116.  
  117. Upper-level Algorithm:
  118.  
  119.     set every element in board[][] to C4_NONE
  120.     set every element in stats[][] to 1
  121.     set player to either 0 or 1
  122.  
  123.     while game is not over
  124.         col = get_desired_col(player)
  125.         drop_piece(player, col)
  126.  
  127.         if is_winner(player) or is_tie()
  128.             game is over
  129.         endif
  130.  
  131.         player = 1 - player
  132.     endwhile
  133.  
  134. -----------------------------------------------------------------------------
  135.  
  136. get_desired_col(player):
  137.     if player is human
  138.         return number from user interface
  139.     else
  140.         return best_move(player, level[player])
  141.     endif
  142.  
  143. -----------------------------------------------------------------------------
  144.  
  145. best_move(player, depth):  /* recursive! */
  146.     minimax search of possible future board states, using alpha-beta
  147.     cutoff techniques to limit unnecessary searches.  Look up these
  148.     techniques in any AI book.  The "goodness" of a board state at any
  149.     point in time, from the point of view of the current player, is equal to
  150.     score(player) - score(1-player), where score(p) = sum of stats[p].
  151.  
  152. -----------------------------------------------------------------------------
  153.  
  154. drop_piece(player, col):
  155.     row = row the token will end up in after falling down the column
  156.     board[col][row] = player
  157.     for each element q in map[col][row]
  158.         stats[player][q] = stats[player][q] * 2
  159.         stats[1-player][q] = 0
  160.     endfor
  161.  
  162. -----------------------------------------------------------------------------
  163.  
  164. is_winner(player):
  165.     for each element s in stats[player]
  166.         if s = 2^n then return TRUE
  167.     endfor
  168.     return FALSE
  169.  
  170. -----------------------------------------------------------------------------
  171.  
  172. is_tie():
  173.     if no element of board[][] is C4_NONE
  174.         return TRUE
  175.     else
  176.         return FALSE
  177.     endif
  178.  
  179. -----------------------------------------------------------------------------
  180.  
  181. sample map[x][y] for x = 6, y = 7, and n = 4:
  182.  
  183.     +---------+---------+---------+---------+---------+---------+---------+
  184.     |20,26,59 |20,21,29,|20,21,22,|20,21,22,|21,22,23,|22,23,41,|23,44,56 |
  185.     |         |62       |32,65    |23,35,47,|38,50    |53       |         |
  186.   5 |         |         |         |68       |         |         |         |
  187.     |         |         |         |         |         |         |         |
  188.     |         |         |         |         |         |         |         |
  189.     +---------+---------+---------+---------+---------+---------+---------+
  190.     |16,25,26,|16,17,28,|16,17,18,|16,17,18,|17,18,19,|18,19,40,|19,43,44,|
  191.     |58       |29,59,61 |31,32,47,|19,34,35,|37,38,49,|41,52,56 |55       |
  192.   4 |         |         |62,64    |46,50,65,|53,68    |         |         |
  193.     |         |         |         |67       |         |         |         |
  194.     |         |         |         |         |         |         |         |
  195.     +---------+---------+---------+---------+---------+---------+---------+
  196.     |12,24,25,|12,13,27,|12,13,14,|12,13,14,|13,14,15,|14,15,39,|15,42,43,|
  197.     |26,57    |28,29,47,|30,31,32,|15,33,34,|36,37,38,|40,41,51,|44,54    |
  198.   3 |         |58,60    |46,50,59,|35,45,49,|48,52,56,|55,68    |         |
  199.     |         |         |61,63    |53,62,64,|65,67    |         |         |
  200.     |         |         |         |66       |         |         |         |
  201.     +---------+---------+---------+---------+---------+---------+---------+
  202.     |8,24,25, |8,9,27,  |8,9,10,  |8,9,10,  |9,10,11, |10,11,39,|11,42,43,|
  203.     |26,47    |28,29,46,|30,31,32,|11,33,34,|36,37,38,|40,41,54,|44,68    |
  204.   2 |         |50,57    |45,49,53,|35,48,52,|51,55,62,|65,67    |         |
  205.     |         |         |58,60    |56,59,61,|64,66    |         |         |
  206.     |         |         |         |63       |         |         |         |
  207.     +---------+---------+---------+---------+---------+---------+---------+
  208.     |4,24,25, |4,5,27,  |4,5,6,30,|4,5,6,7, |5,6,7,36,|6,7,39,  |7,42,43, |
  209.     |46       |28,45,49 |31,48,52,|33,34,51,|37,54,61,|40,64,66 |67       |
  210.   1 |         |         |57       |55,58,60 |63       |         |         |
  211.     |         |         |         |         |         |         |         |
  212.     |         |         |         |         |         |         |         |
  213.     +---------+---------+---------+---------+---------+---------+---------+
  214.     |0,24,45  |0,1,27,  |0,1,2,30,|0,1,2,3, |1,2,3,36,|2,3,39,63|3,42,66  |
  215.     |         |48       |51       |33,54,57 |60       |         |         |
  216.   0 |         |         |         |         |         |         |         |
  217.     |         |         |         |         |         |         |         |
  218.     |         |         |         |         |         |         |         |
  219.     +---------+---------+---------+---------+---------+---------+---------+
  220.  
  221.          0         1         2         3         4         5         6
  222.  
  223.  0 - 23: horizontal wins
  224. 24 - 44: vertical wins
  225. 45 - 56: forward diagonal wins
  226. 57 - 68: backward diagonal wins
  227.  
  228.